Search results for "Abelian repetition"

showing 3 items of 3 documents

Quasi-linear time computation of the abelian periods of a word

2012

Abelian period Abelian repetition weak repetition design of algorithms text algorithms combinatorics on words
researchProduct

Computing abelian periods in words

2011

International audience

Abelian period Abelian repetition weak repetition design of algorithms text algorithms combinatorics on words[INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS]ComputingMilieux_MISCELLANEOUS
researchProduct

Algorithms for Computing Abelian Periods of Words

2012

Constantinescu and Ilie (Bulletin EATCS 89, 167--170, 2006) introduced the notion of an \emph{Abelian period} of a word. A word of length $n$ over an alphabet of size $\sigma$ can have $\Theta(n^{2})$ distinct Abelian periods. The Brute-Force algorithm computes all the Abelian periods of a word in time $O(n^2 \times \sigma)$ using $O(n \times \sigma)$ space. We present an off-line algorithm based on a $\sel$ function having the same worst-case theoretical complexity as the Brute-Force one, but outperforming it in practice. We then present on-line algorithms that also enable to compute all the Abelian periods of all the prefixes of $w$.

FOS: Computer and information sciencesDiscrete Mathematics (cs.DM)Abelian repetitionElementary abelian groupRank of an abelian groupCombinatoricsComputer Science - Data Structures and AlgorithmsFOS: MathematicsDiscrete Mathematics and CombinatoricsMathematics - CombinatoricsData Structures and Algorithms (cs.DS)Abelian groupOnline algorithmMathematicsArithmetic of abelian varietiesDiscrete mathematicsCombinatorics on wordsApplied MathematicsAbelian periodText algorithmWeak repetitionPrefixCombinatorics on wordsDesign of algorithmCombinatorics (math.CO)AlgorithmWord (computer architecture)Computer Science::Formal Languages and Automata TheoryComputer Science - Discrete Mathematics
researchProduct